package com.sicheng.datastruct.tree.search;

import com.sicheng.datastruct.tree.HeroNode;
import com.sicheng.datastruct.tree.utils.TreeUtil;
import lombok.Data;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/28 10:36
 */

@Data
public class SearchTree {
    private HeroNode root;

    public HeroNode initSearchTree(int[] data) {

        if (data == null || data.length == 0)
            return null;
        root = new HeroNode(data[0]);

        if (data.length > 1) {
            for (int i = 1; i < data.length; i++) {
                int val = data[i];
                HeroNode parent = getParent(root, val);
                if (val < parent.no) {
                    parent.left = new HeroNode(val);
                } else
                    parent.right = new HeroNode(val);
            }
        }

        return root;
    }

    private HeroNode getParent(HeroNode root, int val) {
        if (root.left != null && val < root.no)
            return getParent(root.left, val);
        if (root.right != null && val > root.no)
            return getParent(root.right, val);

        return root;
    }


    public static HeroNode lowestCommonAncestor(HeroNode root, int v1, int v2) {
        if (root == null)
            return null;
        if (root.no > v1 && root.no > v2)
            return lowestCommonAncestor(root.left, v1, v2);
        if (root.no < v1 && root.no < v2)
            return lowestCommonAncestor(root.right, v1, v2);

        return root;

    }

    public static void main(String[] args) {
        HeroNode root = new SearchTree().initSearchTree(new int[]{4, 2, 6, 1, 3, 5, 7});

        root.preOrder();

        HeroNode commonAncestor = lowestCommonAncestor(root, 1, 3);

        System.out.println("==================");
        System.out.println(commonAncestor);

        TreeUtil.listFromTopToBottom(root).forEach(System.out::println);
    }

}
